1. Field of the Invention
The present invention relates to a curve generating apparatus and method and to a storage medium storing a curve generating program, as well as to a method of setting associate points, suitable for use in a CAD (Computer Aided Design), computer graphics and image edition, for the purpose of enabling edition of curves representing contours of objects contained in images displayed on a computer.
2. Description of the Related Arts
A motion picture or moving image is composed of a plurality of frames of image data each of which contains an object. The profile or contour of such an object is extracted by a technique known as a contour extraction. Such a contour extraction technique is used mainly in the field of image processing technologies such as CAD, graphics, and so forth. Image synthesizing processing is one of such image processing technologies. The image synthesizing processing often requires contour extraction processing which generates a key signal from the contour of an object. When this technique is used, it is important that the key signal is correctly generated to enable generation of contour curves that exactly express the contour. The key signal provides information for scissoring or cutting out a foreground to be synthesized, and is referred to also as a xe2x80x9cmaskxe2x80x9d.
The above-described contour extraction processing includes a processing for forming a contour curve based on detailed information given by an operator in regard to the contour position and direction of an object and, hence, requires an interactive operation. Various types of contour extraction techniques have been known and proposed, such as a technique in which a plurality of points are appointed on the contour of an object so that contours of sections between adjacent points are formed, a technique which operates control points on parametric curves representing a contour outline, and a technique which permits a contour to be directly input by a user by means of a pointing device such as a mouse. For further detail and examples of the contour extraction techniques, a reference be made to Intelligent Scissors for Image Composition, Eric N. Mortensen and William A. Barrett, Computer Graphics Proceedings, Annual Conference Series, 1995, ACM SIGGRAPE, PP. 191-198., as well as to IMAGE CONTOUR DETECTION METHOD (Japanese Unexamined Patent Publication No. 4-152481 and METHOD OF AND APPARATUS FOR FORMING SCISSORING MASK (Japanese Unexamined Patent Publication No. 4-254854).
With the known contour extraction techniques mentioned above, it is necessary that contour curves be formed accurately on each of many elementary pictures or frames that constitute the moving image. For instance, movie or TV motion pictures lasting several seconds require several hundreds of key signals. Thus, the amount of data to be processed is enormous. Therefore, in the field of movies or TV, it is highly desirable that contour curves for the frames constituting a moving picture be generated as accurately as possible with minimal processing, in view of known contour extraction processing which requires much labor and time.
Under these circumstances, a simplified method for generating contour curves has been proposed which is based on an assumption that a contour curve contained in the starting frame of a continuous motion picture is progressively deformed with time into the contour curve in the ending frame of the motion picture. Thus, an intermediate curve which represents the contour curve of the object in a transient frame is generated by interpolation, based on the contour curve contained in the starting frame and the contour curve contained in the ending frame.
More specifically, in accordance with this interpolation method, each of points constituting the starting frame is correlated to corresponding one of points on the contour curve of the ending frame. It is assumed here that a contour contained in the starting frame is represented by a curve xe2x80x9caxe2x80x9d, while the contour contained in the ending frame is represented by a curve xe2x80x9cbxe2x80x9d. The moment at which the starting frame is displayed is xe2x80x9c0xe2x80x9d, and the moment at which the ending frame is displayed is xe2x80x9c1xe2x80x9d. Assuming that the contour curve changes with time, it is understood that the contour represented by the curve xe2x80x9caxe2x80x9d at the moment xe2x80x9c0xe2x80x9d has been changed to the curve xe2x80x9cbxe2x80x9d by the moment xe2x80x9c1xe2x80x9d. The moment of a transient frame containing the contour to be formed by interpolation is expressed by xe2x80x9cTxe2x80x9d. The coordinates of a point on the curve xe2x80x9caxe2x80x9d is expressed as xe2x80x9cAxe2x80x9d, while the coordinates of the corresponding point on the curve xe2x80x9cbxe2x80x9d is expressed by xe2x80x9cBxe2x80x9d. The coordinates of the corresponding point on the curve in the transient frame is expressed by xe2x80x9cCxe2x80x9d. With these definitions, the coordinates C is given by the following formula.
C=Txc2x7A+(1xe2x88x92T)xc2x7B
In the known interpolation techniques, the contour to be contained in an intermediate or transient frame is formed based on points determined by the described interpolation technique.
The contour curve contained in each frame is constituted by a plurality of cubic Bezier curves. The cubic Bezier curve is defined as follows, as described in a literature COMPUTER GRAPHICS PRINCIPLE AND PRACTICE SECOND EDITION in C (Foley, van Dam. Feiner. Hughes, ADDISON WESLEY, 1996, ISBN 0-201-84840-6.       Q    ⁡          (      t      )        =                    (                              (                          1              -              t                        )                    3                )            ⁢      M        +          3      ⁢              t        ⁡                  (                                    (                              1                -                t                            )                        2                    )                    ⁢      N        +          3      ⁢              (                  t          2                )            ⁢              (                  1          -          t                )            ⁢      O        +                  (                  t          3                )            ⁢              P        ⁢                  
                (                  0          ⁢                      xe2x80x83                    ⁢          t          ⁢                      xe2x80x83                    ⁢          1                )            
Symbols xe2x80x9cMxe2x80x9d, xe2x80x9cNxe2x80x9d, xe2x80x9cOxe2x80x9d and xe2x80x9cPxe2x80x9d indicate coordinates of points on a two-dimensional plane. More specifically, xe2x80x9cMxe2x80x9d and xe2x80x9cPxe2x80x9d represent coordinates of end points of a line, while xe2x80x9cNxe2x80x9d and xe2x80x9cOxe2x80x9d represent coordinates of control points. FIG. 52 shows an example of a line on a cubic Bezier curve expressed by the formula shown above. Referring to FIG. 52, a solid-line curve is the cubic Bezier curve. Points xe2x80x9cMxe2x80x9d and xe2x80x9cPxe2x80x9d indicated by solid circles are end points, while xe2x80x9cNxe2x80x9d and xe2x80x9cOxe2x80x9d indicated by white blank circles are control points.
In accordance with the aforesaid formula that defines the cubic Bezier curve, the locus of the Bezier curve, i.e., a configuration, can be expressed in terms of the coordinates of the end points xe2x80x9cMxe2x80x9d and xe2x80x9cPxe2x80x9d, coordinates of the control points xe2x80x9cOxe2x80x9d and xe2x80x9cNxe2x80x9d, and the change of the time xe2x80x9ctxe2x80x9d.
The unit of the cubic Bezier curve shown in FIG. 52 constitutes a segment of a curve representing a contour curve. Thus, as shown in FIG. 53, a single curve representing a contour curve is composed of a plurality of segments 201. It will be seen that the train of segments forms the single contour line, with adjoining segments 201 commonly possessing an end point 202.
In this known contour extraction technique, an intermediate or transient contour is determined by interpolation based on the contour curve of the frame preceding the transient frame and the contour curve of the frame which trails the transient frame. In this technique, therefore, contour curves of different frames are correlated to each other by the end points and control points of each of the segments. This requires that the contour curves of different frames essentially have the same number of segments.
Actually, the number of segments varies in accordance with the degree of complication and size of the contour curve. However, according to the conventional interpolation technique, segments 201 of the same number are employed, even when significant differences in size and shape exist between the contour curve of the starting frame and that of the ending frame significantly differ as shown in FIG. 54.
Thus, in generating the contour curve of a transient frame by using the conventional interpolation technique, the user is obliged to unnecessarily add end points 203 to the frame containing the contour having fewer segments, in order to equalize the number of the segments 201 of the starting frame and that of the ending frame.
More specifically, referring to FIG. 54A, it is assumed that the contour curve of the starting frame has eight segments with eight associate points 202, while the contour curve of the ending frame has three segments with three associate points 202. In such a case, the user is obliged to edit the contour curve contained in the ending frame so as to add four points 203 as indicated by white blank squares in FIG. 54B, thus creating an ending frame contour curve having four segments 201.
This editorial work undesirably burdens the user. The burden of the editorial work for equalizing the numbers of segments is serious particularly when the contour is complicated.
It is also to be noted that, in the described known technique for generating the contour curve of a transient frame by interpolation, it is desirable that the number of the associate points on the contour curve in the starting frame and that in the ending frames are equal to each other, in order to correlate the contour curves of the starting and ending frames.
In some cases, however, a portion of the contour curve that covers only a small region of an image has been changed to cover a greater proportion of the image in the ending frame. For instance, referring to FIG. 55, only a right portion encircled by 210 expands with time while the major portion of the contour curve xe2x80x9caxe2x80x9d remains unchanged, so as to form a contour xe2x80x9cbxe2x80x9d. In such a case, formation of the contour curve of a transient frame by the known technique encounters with the following problem.
Namely, by the known interpolation technique, the major part of the contour xe2x80x9caxe2x80x9d on the left side of the circle also is inevitably deformed significantly, as will be seen from FIG. 56.
FIG. 57 illustrates a process in which transient curves are determined based on a contour xe2x80x9caxe2x80x9d composed of four segments and a contour xe2x80x9cbxe2x80x9d having eight segments, while suppressing as much as deformation of the portion of the contour xe2x80x9caxe2x80x9d which is on the left side of the portion encircled by a circle 210. This process requires setting of a plurality of end points on the portion 210 of the contour xe2x80x9caxe2x80x9d, as will be seen from FIG. 58. This work is highly laborious and troublesome.
Accordingly, an object of the present invention is to provide a method and an apparatus for generating curves, as well as a storage medium storing a curve generating program, which enables generation of transient curves with high degree of quality, despite any difference in the number of segments between the starting contour and the ending contour.
It is also an object of the present invention to provide a method which is used in the generation of transient curves, for setting associate points on the respective curves.
To these ends, according to one aspect of the present invention, there is provided a curve generating apparatus for generating a curve, comprising: sampling means for setting sampling points on a first closed curve representing the contour of an object contained in an image, and for setting sampling points on a second closed curve which shows the contour of the object after lapse of a predetermined time; associate point setting means for setting associate points that correlate the first and second closed curves; and interpolating means for effecting interpolation between the sampling points set by the sampling means, starting from the associate points set by the associate points setting means, thereby generating a transient closed curve which is transient in the course of deformation of the first closed curve into the second closed curve.
The curve generating apparatus having the features set forth above sets sampling points on the first and second closed curves and sets also associate points on both closed curves. Interpolation is effected between the successive sampling points on the first closed curve and those on the second closed curve, starting from associate points set on these two closed curves, whereby a closed curve is generated to represent a transient contour which is transient in the course of deformation from the first closed curve to the second closed curve.
In accordance with another aspect of the present invention, there is provided a curve generating method comprising: a sampling step for setting sampling points on a first closed curve representing the contour of an object contained in an image, and for setting sampling points on a second closed curve which shows the contour of the object after lapse of a predetermined time; an associate point setting step for setting associate points that correlate the first and second closed curves; and an interpolating step for effecting interpolation between the sampling points set by the sampling means, starting from the associate points set in the associate points setting step, thereby generating a transient closed curve which is transient in the course of deformation of the first closed curve into the second closed curve.
In accordance with the curve generating method having the described features, sampling points are set on the first and second closed curves, as well as the associate points. Interpolation between the successive sampling points on the first closed curve and those on the second closed curve is performed starting from the associate points set on these closed curves, whereby a closed curve is generated to represent an intermediate contour which is transient in the course of deformation from the first closed curve to the second closed curve.
In accordance with still another aspect of the present invention, there is provided a storage medium storing a program which executes: a sampling step for setting sampling points on a first closed curve representing the contour of an object contained in an image, and for setting sampling points on a second closed curve which shows the contour of the object after lapse of a predetermined time; an associate point setting step for setting associate points that correlate the first and second closed curves; and an interpolating step for effecting interpolation between the sampling points set by the sampling means starting from the associate points set in the associate points setting step, thereby generating a transient closed curve which is transient in the course of deformation of the first closed curve into the second closed curve.
This storage medium, when used on a computer, loads the computer with the program. The program serves to set sampling points on the first and second closed curves, as well as associate points. The program executes interpolation between successive sampling points on the first closed curve and those on the second closed curve, starting from associate points set on these two curves, whereby a closed curve is generated to represent an intermediate contour which is transient in the course of deformation from the first closed curve to the second closed curve.
In accordance with a further aspect of the present invention, there is provided a method of setting associate points, comprising the steps of: detecting curvatures of a first closed curve representing the contour of an object contained in an image and detecting curvatures of a second closed curve representing the contour of the object after lapse of a predetermined time; comparing the peak values of the curvatures detected on the first closed curve and peak values of the curvatures detected on the second closed curve with a predetermined threshold, and extracting, as detected points, points on the first and second closed curves which exhibit curvature peak values not smaller than the threshold values; and setting, as associate points, one of the detected point on one of the first and second closed curves and one of the detected points on the other closed curve which is near to the above-mentioned one of the detected points on one of the first and second closed curves, when the curvatures at the detected points on both closed curves have the same sign of plus or minus.
According to this method, peak values of the curvatures of both the first and second closed curves are compared with a threshold value. Points on both closed curves where curvature peak values not smaller than the threshold value are exhibited are extracted as detected points. A pair of points, composed of a first point which is one of the detected points on one of two closed curves and a second point which is one of the detected points on the other closed curve and near the first point, are set as being associate points if the curvatures at these first and second points have the same sign of plus or minus.